#include <stdio.h>
#include <stdlib.h>
#include <cctype>
#include <string>
#include <iostream>
#include <vector>

// Type Declarations

enum PrintBehavior {
    CloseAtSameLine,
    CloseAtOtherLine
};

typedef std::string Symbol;
typedef std::vector<Symbol> SymTab;
typedef SymTab* TabPtr;

/* Variable Declarations */
char        Look;               // Lookahead Character
char        Token;              // Encoded Token
Symbol      Value;              // Unencoded Token
SymTab      ST;
std::string SType;
int         LCount  = 0;        // Label Count
const int   buf_len = 64;
int         DLevel  = 0;        // Debug log level

// Definition of Keywords and Token Types
SymTab KWlist{
    "IF", "ELSE", "ENDIF", "WHILE", "ENDWHILE",
        "READ", "WRITE", "VAR", "BEGIN", "END", "PROGRAM"};

// The 'x' in KWcode identify error(or to say, not keyword) 
std::string KWcode("xileweRWvbep");

// Table Lookup

// If the input string matches a table entry, return the entry index.
// If not, return a -1.

int Lookup(const TabPtr T, const Symbol& s) {
    for (int i = 0; i < T->size(); ++i) {
        if (s == (*T)[i]) {
            return i;
        }
    }
    return -1;
}

void GetName(); // Forward Declaration
void Store(const Symbol& Name);

// Get an Identifier and Scan it for Keywords
void Scan() {
    GetName();
    Token = KWcode[Lookup(&KWlist, Value) + 1];
}

/* Print Token. Usage: PrintEnter(Token, CloseAtOtherLine/CloseAtSameLine).
   If CloseAtOtherLine, when going out of the Token name scope, you must call PrintLeave().
*/
void PrintEnter(const char* s, PrintBehavior behavior = CloseAtOtherLine) {
    for (int i = 0; i < DLevel; ++i) {
        printf("\t");
    }
    printf("<%s", s);
    if (behavior == CloseAtSameLine) {
        printf(">\n");
    }
    else {
        printf("\n");
        ++DLevel;
    }
}

void PrintLeave() {
    for (int i = 1; i < DLevel; ++i) {
        printf("\t", DLevel);
    }
    printf(">\n");
    --DLevel;
}

/* Report an Error */
template<typename T>
void WriteLn(const T& t) {
    std::cout << t << std::endl;
}

void Error(const std::string& s) {
    std::cout << std::endl;
    std::cout << "Error: " << s << "." << std::endl;
}

/* Report Error and Halt */
void Abort(const std::string& s) {
    Error(s);
    exit(0);
}

/* Report What Was Expected */
void Expected(const std::string& s) {
    Abort(s + " Expected");
}

// Report an Undefined Identifier
void Undefined(const std::string& n) {
    Abort("Undefined Identifier " + n);
}

/* Output a String with Tab */
void EmitLn(const std::string& s) {
    std::cout << "\t " << s << std::endl;
}

// Look for Symbol in Table
bool InTable(const Symbol& n) {
    return (Lookup(&ST, n) != -1);
}

// Clear the Primary Register
void Clear() {
    EmitLn("CLR D0");
}

// Negate the Primary Register
void Negate() {
    EmitLn("NEG D0");
}

// Load a Constant Value to Primary Register
void LoadConst(int n) {
    std::cout << "\t MOVE #";
    std::cout << n << ",D0" << std::endl;
}

// Load a Variable to Primary Register
void LoadVar(const Symbol& Name) {
    if (!InTable(Name)) {
        Undefined(Name);
    }
    EmitLn(std::string("MOVE ") + Name + "(PC),D0");
}

// Read Variable to Primary Register
void ReadVar() {
    EmitLn("BSR READ");
    Store(Value);
}

// Write Variable from Primary Register
void WriteVar() {
    EmitLn("BSR WRITE");
}

// Push Primary onto Stack
void Push() {
    EmitLn("MOVE D0,-(SP)");
}

// Add Top of Stack to Primary
void PopAdd() {
    EmitLn("ADD (SP)+,D0");
}

// Subtract Primary from Top of Stack
void PopSub() {
    EmitLn("SUB (SP)+,D0");
    EmitLn("NEG D0");
}

// Multiply Top of Stack by Primary
void PopMul() {
    EmitLn("MULS (SP)+,D0");
}

// Divide Top of Stack by Primary
void PopDiv() {
    EmitLn("MOVE (SP)+,D7");
    EmitLn("EXT.L D7");
    EmitLn("DIVS D0,D7");
    EmitLn("MOVE D7,D0");
}

// Store Primary to Variable
void Store(const Symbol& Name) {
    if (!InTable(Name)) {
        Undefined(Name);
    }
    EmitLn(std::string("LEA ") + Name + "(PC),A0");
    EmitLn("MOVE D0,(A0)");
}

/* Read New Character From Input Stream */
void GetChar() {
    Look = getchar();
}

// Generate a Unique Label
std::string NewLabel() {
    char buf[buf_len] = {0};
    sprintf(buf, "L%d", LCount);
    LCount++;

    return buf;
}

// Post a Label To Output
void PostLabel(const std::string& L) {
    WriteLn(L + ":");
}

/* Recognize White Space */
int IsWhite(char c) {
    if (c==' ' ||
        c=='\t') {
        return 1;
    }
    else {
        return 0;
    }
    // return isspace(c);
}

/* Skip Over Leading White Space */
void SkipWhite() {
    while (IsWhite(Look)) {
        GetChar();
    }
}

// Skip Over a Comma
void SkipComma() {
    SkipWhite();
    if (Look == ',') {
        GetChar();
        SkipWhite();
    }
}

// Skip a CRLF
void Fin() {
    while ((Look == '\n') || (Look == '\r')) {
        GetChar();
    }
    SkipWhite();
}

// Skip Over an End-of-Line
void NewLine() {
    Fin();
}

/* Match a Specific Input Character */
void Match(char x) {
    if (Look == x) {
        GetChar();
        SkipWhite();
    }
    else {
        char buf[buf_len] = {0};
        sprintf(buf, "'''' %c ''''", x);
        Expected(buf);
    }
}

// Match a Specific Input String
void MatchString(const std::string& x) {
    if (Value != x) {
        Expected("''''" + x + "''''");
    }
}

/* Recognize an Alpha Character  */
int IsAlpha(char c) {
    return isalpha(c);
}

/* Recognize a Decimal Digit */
int IsDigit(char c) {
    return isdigit(c);
}

/* Recognize an Alphanumeric Character */
int IsAlNum(char c) {
    return (IsAlpha(c) || IsDigit(c));
}

/* Recognize an Addop */
int IsAddop(char c) {
    if ((c == '+') ||
        (c == '-')) {
        return 1;
    }
    else {
        return 0;
    }
}

// Recognize a Mulop
int IsMulop(char c) {
    if ((c == '*') ||
        (c == '/')) {
        return 1;
    }
    else {
        return 0;
    }
}

bool IsOrOp(char c) {
    if (c == '|' ||
        c == '~') {
        return true;
    }
    else {
        return false;
    }
}

/* Get an Identifier */
void GetName() {
    NewLine();
    if (!IsAlpha(Look)) {
        Expected("Name");
    }

    Value = "";
    while (IsAlNum(Look)) {
        Value += toupper(Look);
        GetChar();
    }

    SkipWhite();
}

/* Get a Number */
int GetNum() {
  if (!IsDigit(Look)) {
	Expected("Integer");
  }

  int Val = 0;
  while (IsDigit(Look)) {
      Val = 10 * Val + (Look - '0');
      GetChar();
  }

  return Val;
}

// Add a New Entry to Symbol Table. N is variable name, T is TokenType.
void AddEntry(const Symbol& N, char T) {
    if (InTable(N)) {
        Abort("Duplicate Identifier " + N);
    }
    ST.push_back(N);
    SType.push_back(T);
}

// Allocate Storage for a Variable
void Alloc(const Symbol& N) {
    if (InTable(N)) {
        Abort(std::string("Duplicate Variable Name ") + N);
    }
    AddEntry(N, 'v');

    std::cout << N << ":\t" << "DC ";
    if (Look == '=') {
        Match('=');
        if (Look == '-') {
            std::cout << Look;
            Match('-');
        }
        std::cout << GetNum() << std::endl;
    }
    else {
        std::cout << '0' << std::endl;
    }
}

// Write Header Info REQUIRED by Assembler
void Header() {
    WriteLn("WARMST\tEQU $A01E");
    EmitLn("LIB TINYLIB");
}

// Write the Prolog
void Prolog() {
    PostLabel("MAIN");
}

// Write the Epilog
void Epilog() {
    EmitLn("DC WARMST");
    EmitLn("END MAIN");
}

// Parse and Translate a Data Declaration
void Decl() {
    GetName();
    Alloc(Value);
    while (Look == ',') {
        // GetChar();              // 这一行代码与下一行代码等价，但效率高。因为Match肯定成功。
        Match(',');             // Match与GetChar并不等价，这里只能用Match，因为Match会过滤老鼠屎
        // Ident();
        GetName();
        Alloc(Value);
    }
}

// Parse and Translate Global Declarations
void TopDecls() {
    
    Scan();
    while (Token != 'b') {
        switch (Token) {
        case 'v':
            Decl();
            break;
        default:
            Abort(std::string("Unrecognized Keyword '") + Value + "'");
        }

        Scan();
    }
}

// Forward declaration
void Block();
void Expression();
void BoolExpression();

// Parse and Translate a Math Factor
void Factor() {
    if (Look == '(') {
        Match('(');
        BoolExpression();
        Match(')');
    }
    else if (IsAlpha(Look)) {
        GetName();
        LoadVar(Value);
    }
    else {
        LoadConst(GetNum());
    }
}

// Parse and Translate a Negative Factor
void NegFactor() {
    Match('-');
    if (IsDigit(Look)) {
        LoadConst(-GetNum());
    }
    else {
        Factor();
        Negate();
    }
}

// Parse and Translate a Leading Factor
void FirstFactor() {
    switch (Look) {
    case '+': {
        Match('+');
        Factor();
        break;
    }
    case '-': {
        NegFactor();
        break;
    }
    default:
        Factor();
        break;
    }
}

// Recognize and Translate a Multiply
void Multiply() {
    Match('*');
    Factor();
    PopMul();
}

// Recognize and Translate a Divide
void Divide() {
    Match('/');
    Factor();
    PopDiv();
}

// Common Code Used by Term and FirstTerm
void Term1() {
    while (IsMulop(Look)) {
        Push();
        if (Look == '*') {
            Multiply();
        }
        else if (Look == '/') {
            Divide();
        }
        else {
            Abort("Must be Mulop");
        }
    }
}

// Parse and Translate a Math Term
void Term() {
    Factor();
    Term1();
}

// Parse and Translate a Leading Term
void FirstTerm() {
    FirstFactor();
    Term1();
}

// Recognize and Translate an Add
void Add() {
    Match('+');
    Term();
    PopAdd();
}

// Recognize and Translate a Subtract
void Subtract() {
    Match('-');
    Term();
    PopSub();
}

// Recognize a Relop
bool IsRelop(char c) {
    if (c == '=' ||
        c == '#' ||
        c == '<' ||
        c == '>') {
        return true;
    }
    else {
        return false;
    }
}

// Complement the Primary Register
void NotIt() {
    EmitLn("NOT D0");
}

// AND Top of Stack with Primary
void PopAnd() {
    EmitLn("AND (SP)+,D0");
}

// OR Top of Stack with Primary
void PopOr() {
    EmitLn("OR (SP)+,D0");
}

// XOR Top of Stack with Primary
void PopXor() {
    EmitLn("EOR (SP)+,D0");
}

// Compare Top of Stack with Primary
void PopCompare() {
    EmitLn("CMP (SP)+,D0");
}

// Set D0 If Compare was =
void SetEqual() {
    EmitLn("SEQ D0");
    EmitLn("EXT D0");
}

// Set D0 If Compare was !=
void SetNEqual() {
    EmitLn("SNE D0");
    EmitLn("EXT D0");
}

// Set D0 If Compare was >
void SetGreater() {
    EmitLn("SGT D0");
    EmitLn("EXT D0");
}

// Set D0 If Compare was <
void SetLess() {
    EmitLn("SLT D0");
    EmitLn("EXT D0");
}

// Set D0 If Compare was <=
void SetLessOrEqual() {
    EmitLn("SGE D0");
    EmitLn("EXT D0");
}

// Set D0 If Compare was >=
void SetGreaterOrEqual() {
    EmitLn("SLE D0");
    EmitLn("EXT D0");
}

// Recognize and Translate a Relational "Equals"
void Equals() {
    Match('=');
    Expression();
    PopCompare();
    SetEqual();
}

// Recognize and Translate a Relational "Not Equals"
void NotEquals() {
    Match('>');
    Expression();
    PopCompare();
    SetNEqual();
}

// Recognize and Translate a Relational "Less Than or Equal"
void LessOrEqual() {
    Match('=');
    Expression();
    PopCompare();
    SetLessOrEqual();
}

// Recognize and Translate a Relational "Greater Than or Equal"
void GreaterOrEqual() {
    Match('=');
    Expression();
    PopCompare();
    SetGreaterOrEqual();
}

// Recognize and Translate a Relational "Less Than"
void Less() {
    Match('<');
    if (Look == '=') {
        LessOrEqual();
    }
    else if (Look == '>') {
        NotEquals();
    }
    else {
        Expression();
        PopCompare();
        SetLess();
    }
}

// Recognize and Translate a Relational "Greater Than"
void Greater() {
    Match('>');
    if (Look == '=') {
        GreaterOrEqual();
    }
    else {
        Expression();
        PopCompare();
        SetGreater();
    }
}

// Parse and Translate a Relation
void Relation() {
    Expression();
    if (IsRelop(Look)) {
        Push();
        if (Look == '=') {
            Equals();
        }
        else if (Look == '<') {
            Less();
        }
        else if (Look == '>') {
            Greater();
        }
    }
}

// Parse and Translate a Boolean Factor with Leading NOT
void NotFactor() {
    if (Look == '!') {
        Match('!');
        Relation();
        NotIt();
    }
    else {
        Relation();
    }
}

// Parse and Translate a Boolean Term
void BoolTerm() {
    NotFactor();
    while (Look == '&') {
        Push();
        Match('&');
        NotFactor();
        PopAnd();
    }
}

// Recognize and Translate a Boolean OR
void BoolOr() {
    Match('|');
    BoolTerm();
    PopOr();
}

// Recognize and Translate an Exclusive Or
void BoolXor() {
    Match('~');
    BoolTerm();
    PopXor();
}

// Parse and Translate a Boolean Expression
void BoolExpression() {
    BoolTerm();
    while (IsOrOp(Look)) {
        Push();
        if (Look == '|') {
            BoolOr();
        }
        else if (Look == '~') {
            BoolXor();
        }
    }
}

// Parse and Translate an Expression
void Expression() {
    FirstTerm();
    while (IsAddop(Look)) {
        Push();
        if (Look == '+') {
            Add();
        }
        else if (Look == '-') {
            Subtract();
        }
        else {
            Abort("Must be Addop");
        }
    }
}

// Branch Unconditional
void Branch(const std::string& L) {
    EmitLn("BRA " + L);
}

// Branch False
void BranchFalse(const std::string& L) {
    EmitLn("TST D0");
    EmitLn("BEQ " + L);
}

// Recognize and Translate an IF Construct
void DoIf() {
    std::string L1, L2;
    BoolExpression();
    L1 = NewLabel();
    L2 = L1;
    BranchFalse(L1);
    Block();
    if (Look == 'l') {
        L2 = NewLabel();
        Branch(L2);
        PostLabel(L1);
        Block();
    }
    PostLabel(L2);
    MatchString("ENDIF");
}

// Parse and Translate a WHILE Statement
void DoWhile() {
    std::string L1, L2;
    L1 = NewLabel();
    L2 = NewLabel();
    PostLabel(L1);
    BoolExpression();
    BranchFalse(L2);
    Block();
    MatchString("ENDWHILE");
    Branch(L1);
    PostLabel(L2);
}

// Process a Read Statement
void DoRead() {
    Match('(');
    GetName();
    ReadVar();
    while (Look == ',') {
        Match(',');
        GetName();
        ReadVar();
    }
    Match(')');
}

// Process a Write Statement
void DoWrite() {
    Match('(');
    Expression();
    WriteVar();
    while (Look == ',') {
        Match(',');
        Expression();
        WriteVar();
    }
    Match(')');
}

// Parse and Translate an Assignment Statement
void Assignment() {
    Match('=');
    BoolExpression();
    Store(Value);
}

// Parse and Translate a Block of Statements
void Block() {
    
    Scan();
    while (Token != 'e' && Token != 'l') {
        if (Token == 'i') {
            DoIf();
        }
        else if (Token == 'w') {
            DoWhile();
        }
        else if (Token == 'R') {
            DoRead();
        }
        else if (Token == 'W') {
            DoWrite();
        }
        else {
            Assignment();
        }

        Scan();
    }
}

// Parse and Translate a Main Program
void Main() {
    MatchString("BEGIN");
    Prolog();
    Block();
    MatchString("END");
    Epilog();
}

// Parse and Translate a Program
void Prog() {
    MatchString("PROGRAM");
    Header();
    TopDecls();
    Main();
    Match('.');
}

/* Initialize */
void Init() {
    GetChar();
    Scan();
}

/* Main Program */
int main(int argc, char** argv) {
  Init();

  Prog();
  if (Look != '\n') {
      Abort("Unexpected data after '.'");
  }
  
  return 0;
}
